#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
    // 经典dp
    // dp[i] = max(dp[i],dp[j]+1)
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size()+1,1);
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }
        int ans = -1;
        for (auto tmp:dp){
            ans = max(tmp,ans);
        }
        
        return ans;
    }   
};
int main()
{
    Solution solution;
    vector<int> input = {1,3,6,7,9,4,10,5,6};
    cout<<solution.lengthOfLIS(input)<<endl;
    return 0;
}